//  给定一个整数数组nums， 再给定一个整数k，表示大小为k的滑动窗口从数组的最左侧移动到数组的最右侧，
//  我们只能看到滑动窗口内的k个数字，滑动窗口每次只能向右移动一位
//  要求返回滑动窗口中的最大值

// 思路，单调递减栈，双指针，维护一个单调递减栈，判断栈顶元素和当前元素，如果当前元素大于栈顶元素，则移除，循环判断移除
// 判断栈底元素索引是否超出k的限制，如果是的话，移除栈底
// 时间复杂度：O(n)
// 空间复杂度：O(k)

function maxSlidingWindow(arr, k) {
    const res = []
    const stack = []
    for (let i = 0; i < arr.length; i++) {
        if (i - k >= 0 && i - k === stack[0]) {
            stack.shift()
        }
        while (stack.length && arr[stack[stack.length - 1]] < arr[i]) {
            stack.pop()
        } 
        stack.push(i)
        if (i >= k - 1) {
            res.push(arr[stack[0]])
        }       
    }
    return res
}


let nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

nums = [1]
k = 1
console.log(maxSlidingWindow(nums, k));